package com.lw.leetcode.back.c;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * back
 * c
 * 980. 不同路径 III
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/17 15:30
 */
public class UniquePathsIII {

    private int sum;
    public int uniquePathsIII(int[][] grid) {
        int a = grid.length;
        int b = grid[0].length;
        int x = 0;
        int y = 0;
        int count = 0;
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                int value = grid[i][j];
                if (value == 0) {
                    count++;
                } else if (value == 1) {
                    x = i;
                    y = j;
                }
            }
        }
        find(grid, x + 1, y, count );
        find(grid, x - 1, y, count );
        find(grid, x, y + 1, count );
        find(grid, x, y - 1, count );
        return sum;
    }

    private void find(int[][] grid, int x, int y, int count) {

        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) {
            return;
        }
        int value = grid[x][y];
        if (value == 2 && count == 0) {
            sum++;
            return;
        }
        if (value == -1 || value == 1 || value == 2 || count == 0) {
            return;
        }
        grid[x][y] = -1;
        find(grid, x + 1, y, count - 1);
        find(grid, x - 1, y, count - 1);
        find(grid, x, y + 1, count - 1);
        find(grid, x, y - 1, count - 1);
        grid[x][y] = 0;
    }


}
